Markov odometer

 ( Dynamical Systems ) 

In mathematics, a Markov odometer is a certain type of topological dynamical system. It plays a fundamental role in ergodic theory and especially in orbit theory of dynamical systems, since a theorem of H. Dye asserts that every ergodic nonsingular transformation is orbit-equivalent to a Markov odometer.

The basic example of such system is the "nonsingular odometer", which is an additive topological group defined on the product space of , induced by addition defined as $x\; \backslash mapsto\; x+\backslash underline\{1\}$, where $\backslash underline\{1\}:=(1,0,0,\backslash dots)$. This group can be endowed with the structure of a dynamical system; the result is a conservative dynamical system.

The general form, which is called "Markov odometer", can be constructed through Bratteli–Vershik diagram to define Bratteli–Vershik compactum space together with a corresponding transformation.

---

Nonsingular odometers Several kinds of non-singular odometers may be defined. These are sometimes referred to as adding machines.

(2025). 9780387304403, Springer. ISBN 9780387304403

The simplest is illustrated with the Bernoulli process. This is the set of all infinite strings in two symbols, here denoted by $\backslash Omega=\backslash \{0,1\backslash \}^\{\backslash mathbb\{N\}\}$ endowed with the product topology. This definition extends naturally to a more general odometer defined on the product space

$\backslash Omega=\backslash prod\_\{n\backslash in\backslash mathbb\{N\}\}\; \backslash left(\backslash mathbb\{Z\}/k\_n\backslash mathbb\{Z\}\backslash right)$

for some sequence of integers $(k\_n)$ with each $k\_n\backslash ge\; 2.$

The odometer for $k\_n=2$ for all $n$ is termed the dyadic odometer, the von Neumann–Kakutani adding machine or the dyadic adding machine.

The topological entropy of every adding machine is zero. Any continuous map of an interval with a topological entropy of zero is topologically conjugate to an adding machine, when restricted to its action on the topologically invariant transitive set, with periodic orbits removed.

---

Dyadic odometer The set of all infinite strings in strings in two symbols $\backslash Omega=\backslash \{0,1\backslash \}^\{\backslash mathbb\{N\}\}$ has a natural topology, the product topology, generated by the . The product topology extends to a Borel sigma-algebra; let $\backslash mathcal\{B\}$ denote that algebra. Individual points $x\backslash in\backslash Omega$ are denoted as $x=(x\_1,x\_2,x\_3,\backslash cdots).$

The Bernoulli process is conventionally endowed with a collection of measures, the Bernoulli measures, given by $\backslash mu\_p(x\_n=1)=p$ and $\backslash mu\_p(x\_n=0)=1-p$, for some Haar measure, when $\backslash Omega$ is viewed as a compact space Abelian group. Note that the Bernoulli measure is not the same as the 2-adic measure on the dyadic integers! Formally, one can observe that $\backslash Omega$ is also the base space for the dyadic integers; however, the dyadic integers are endowed with a metric space, the p-adic metric, which induces a metric topology distinct from the product topology used here.

The space $\backslash Omega$ can be endowed with addition, defined as coordinate addition, with a carry bit. That is, for each coordinate, let $(x+y)\_n=x\_n+y\_n+\backslash varepsilon\_n\backslash ,\backslash bmod\backslash ,2$ where $\backslash varepsilon\_0=0$ and

$$

\varepsilon_n=\begin{cases} 0 & x_{n-1}+y_{n-1}<2\\ 1 & x_{n-1}+y_{n-1}=2 \end{cases}

inductively. Increment-by-one is then called the (dyadic) odometer. It is the transformation $T:\backslash Omega\backslash to\backslash Omega$ given by $T(x)=x+\backslash underline\{1\}$, where $\backslash underline\{1\}:=(1,0,0,\backslash dots)$. It is called the odometer due to how it looks when it "rolls over": $T$ is the transformation $T\backslash left(1,\backslash dots,1,0,x\_\{k+1\},x\_\{k+2\},\backslash dots\backslash right)\; =\; \backslash left(0,\backslash dots,0,1,x\_\{k+1\},x\_\{k+2\},\backslash dots\; \backslash right)$. Note that $T^\{-1\}(0,0,\backslash cdots)=(1,1,\backslash cdots)$ and that $T$ is $\backslash mathcal\{B\}$-measurable, that is, $T^\{-1\}(\backslash sigma)\backslash in\backslash mathcal\{B\}$ for all $\backslash sigma\backslash in\backslash mathcal\{B\}.$

The transformation $T$ is non-singular for every $\backslash mu\_p$. Recall that a measurable transformation $\backslash tau:\backslash Omega\backslash to\backslash Omega$ is non-singular when, given $\backslash sigma\backslash in\backslash mathcal\{B\}$, one has that $\backslash mu(\backslash tau^\{-1\}\backslash sigma)=0$ if and only if $\backslash mu(\backslash sigma)=0$. In this case, one finds

$\backslash frac\{d\; \backslash mu\_p\; \backslash circ\; T\}\{d\; \backslash mu\_p\}\; =\; \backslash left(\backslash frac\{1-p\}\; p\backslash right)^\backslash varphi$

where $\backslash varphi(x)=\backslash min\backslash left\backslash \{\; n\backslash in\backslash mathbb\{N\}\backslash mid\; x\_n\; =\; 0\; \backslash right\backslash \}-2$. Hence $T$ is nonsingular with respect to $\backslash mu\_p$.

The transformation $T$ is ergodic. This follows because, for every $x\; \backslash in\; \backslash Omega$ and natural number $n$, the orbit of $x$ under $T^0,T^1,\backslash cdots,T^\{2^n-1\}$ is the set $\backslash \{0,1\backslash \}^n$. This in turn implies that $T$ is conservative, since every invertible ergodic nonsingular transformation in a atomic measure is conservative.

Note that for the special case of $p=1/2$, that $\backslash left(\backslash Omega,\backslash mathcal\{B\},\backslash mu\_\{1/2\},T\backslash right)$ is a measure-preserving dynamical system.

---

Integer odometers The same construction enables to define such a system for every product space of . In general, one writes

$\backslash Omega=\backslash prod\_\{n\backslash in\backslash mathbb\{N\}\}A\_\{n\}$

for $A\_n=\backslash mathbb\{Z\}/m\_n\backslash mathbb\{Z\}=\backslash \{\; 0,1,\backslash dots,m\_n-1\backslash \}$ with $m\_n\backslash ge2$ an integer. The product topology extends naturally to the product Borel sigma-algebra $\backslash mathcal\{B\}$ on $\backslash Omega$. A product measure on $\backslash mathcal\{B\}$ is conventionally defined as $\backslash textstyle\backslash mu=\backslash prod\_\{n\backslash in\backslash mathbb\{N\}\}\backslash mu\_\{n\},$ given some measure $\backslash mu\_n$ on $A\_n$. The corresponding map is defined by

$T(x\_1,\backslash dots,x\_k,x\_\{k+1\},x\_\{k+2\},\backslash dots)=(0,\backslash dots,0,x\_k+1,x\_\{k+1\},x\_\{k+2\},\backslash dots)$

where $k$ is the smallest index for which $x\_k\; \backslash neq\; m\_k-1$. This is again a topological group.

A special case of this is the Ornstein odometer, which is defined on the space

$\backslash Omega=\backslash left(\backslash mathbb\{Z\}/2\backslash mathbb\{Z\}\backslash right)\backslash times\; \backslash left(\backslash mathbb\{Z\}/3\backslash mathbb\{Z\}\backslash right)\backslash times\; \backslash left(\backslash mathbb\{Z\}/4\backslash mathbb\{Z\}\backslash right)\backslash times\; \backslash cdots$

with the measure a product of

$\backslash mu\_n(j)=\backslash begin\{cases\}$

1/2 & \mbox{ if } j=0 \\ 1/2(n+1) & \mbox{ if } j\ne 0 \\ \end{cases}

---

Sandpile model A concept closely related to the conservative odometer is that of the abelian sandpile model. This model replaces the directed linear sequence of finite groups constructed above by an undirected graph $(V,E)$ of vertexes and edges. At each vertex $v\backslash in\; V$ one places a finite group $\backslash mathbb\{Z\}/n\backslash mathbb\{Z\}$ with $n=deg(v)$ the degree of the vertex $v$. Transition functions are defined by the graph Laplacian. That is, one can increment any given vertex by one; when incrementing the largest group element (so that it increments back down to zero), each of the neighboring vertexes are incremented by one.

Sandpile models differ from the above definition of a conservative odometer in three different ways. First, in general, there is no unique vertex singled out as the starting vertex, whereas in the above, the first vertex is the starting vertex; it is the one that is incremented by the transition function. Next, the sandpile models in general use undirected edges, so that the wrapping of the odometer redistributes in all directions. A third difference is that sandpile models are usually not taken on an infinite graph, and that rather, there is one special vertex singled out, the "sink", which absorbs all increments and never wraps. The sink is equivalent to cutting away the infinite parts of an infinite graph, and replacing them by the sink; alternately, as ignoring all changes past that termination point.

---

Markov odometer Let $B=(V,E)$ be an ordered Bratteli–Vershik diagram, consists on a set of vertices of the form $\backslash textstyle\backslash coprod\_\{n\backslash in\backslash mathbb\{N\}\}V^\{(n)\}$ (disjoint union) where $V^0$ is a singleton and on a set of edges $\backslash textstyle\backslash coprod\_\{n\backslash in\backslash mathbb\{N\}\}E^\{(n)\}$ (disjoint union).

The diagram includes source surjection-mappings $s\_n:E^\{(n)\}\; \backslash to\; V^\{(n-1)\}$ and range surjection-mappings $r\_n:E^\{(n)\}\; \backslash to\; V^\{(n)\}$. We assume that $e,e\text{'}\; \backslash in\; E^\{(n)\}$ are comparable if and only if $r\_n(e)\; =\; r\_n(e\text{'})$.

For such diagram we look at the product space $\backslash textstyle\; E:=\backslash prod\_\{n\backslash in\backslash mathbb\{N\}\}E^\{(n)\}$ equipped with the product topology. Define "Bratteli–Vershik compactum" to be the subspace of infinite paths,

$X\_\{B\}:=\backslash left\backslash \{\; x=(x\_n)\_\{n\backslash in\backslash mathbb\{N\}\}\; \backslash in\; E\backslash mid\; x\_n\backslash in\; E^\{(n)\}\backslash text\{\; and\; \}\; r\; (x\_n)\; =\; s(x\_\{n+1\})\; \backslash right\backslash \}$

Assume there exists only one infinite path $x\_\{\backslash max\}\; =\; (x\_n)\_\{n\; \backslash in\; \backslash mathbb\{N\}\}$ for which each $x\_n$ is maximal and similarly one infinite path $x\_\{\backslash text\{min\}\}$. Define the "Bratteli-Vershik map" $T\_B:X\_B\; \backslash to\; X\_B$ by $T(\; x\_\{\backslash max\})\; =\; x\_\{\backslash min\}$ and, for any $x\; =\; (x\_n)\_\{n\backslash in\; \backslash mathbb\{N\}\}\; \backslash neq\; x\_\{\backslash max\}$ define $T\_B(x\_1,\backslash dots,x\_k,x\_\{k+1\},\backslash dots)=(y\_1,\backslash dots,y\_k,x\_\{k+1\},\backslash dots)$, where $k$ is the first index for which $x\_k$ is not maximal and accordingly let $(y\_1,\backslash dots,y\_k)$ be the unique path for which $y\_1,\backslash dots,y\_\{k-1\}$ are all maximal and $y\_k$ is the successor of $x\_k$. Then $T\_B$ is homeomorphism of $X\_B$.

Let $P=\backslash left(P^\{(1)\},P^\{(2)\},\backslash dots\; \backslash right)$ be a sequence of stochastic matrices $P^\{(n)\}=\backslash left(p^\{(n)\}\_\{(v,e)\; \backslash in\; V^\{n-1\}\; \backslash times\; E^(n)\}\backslash right)$ such that $p^\{(n)\}\_\{v,e\}\; >\; 0$ if and only if $v=s\_n(e)$. Define "Markov measure" on the cylinders of $X\_B$ by $\backslash mu\_P\; (e\_1,\backslash dots,e\_n)\; =\; p^\{(1)\}\_\{s\_1(e\_1),e\_1\}\backslash cdots\; p^\{(n)\}\_\{s\_n(e\_n),e\_n\}$. Then the system $\backslash left(X\_B,\; \backslash mathcal\{B\},\; \backslash mu\_P,\; T\_B\; \backslash right)$ is called a "Markov odometer".

One can show that the nonsingular odometer is a Markov odometer where all the $V^\{(n)\}$ are singletons.

---

See also

• Abelian sandpile model

---

Further reading

• J. Aaronson (1997). 9781470412814, American Mathematical Society. ISBN 9781470412814
• Anthony H. Dooley (2025). 9780521533652, Cambridge University Press. ISBN 9780521533652

Post Comment